package leetcode.problems;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by gmwang on 2018/3/9
 */
public class _0310LexicographicalNumbers {
    /**
     * Given an integer n, return 1 - n in lexicographical order.

     For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

     Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

     给定一个整数n，按字典顺序返回1 - n。

     例如，给出13，返回：[1,10,11,12,13,2,3,4,5,6,7,8,9]。

     请优化您的算法以节省时间和空间。输入大小可能高达5,000,000。
     */
    public static List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>(n);
        for (int i = 1, curr = 1; i <= n; ++i) {
            ans.add(curr);
            if (curr * 10 <= n) {
                curr *= 10;
            } else {
                while (curr % 10 == 9 || curr == n) curr /= 10;
                curr++;
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(lexicalOrder(13));
    }
}
